This paper urges the importance of including conditional proof as an inference rule in the teaching of elementary symbolic logic. The paper explains how to make clear to students that conditional proof is valid. This is done by a little proof that shows that hypothetical syllogism (or the chain rule) is both intuitively valid yet redundant. Teaching conditional proof not only aids in a deeper understanding of the meaning of “if” but also provides a strong (...) reminder to the student that they have not proved that the conclusion is true but instead have shown that the conclusion follows from the premises. (shrink)

We prove that the theory IΔ0, extended by a weak version of the Δ0-Pigeonhole Principle, proves that every integer is the sum of four squares (Lagrange's theorem). Since the required weak version is derivable from the theory IΔ0 + ∀x (xlog(x) exists), our results give a positive answer to a question of Macintyre (1986). In the rest of the paper we consider the number-theoretical consequences of a new combinatorial principle, the ‘Δ0-Equipartition Principle’ (Δ0EQ). In particular we give a new (...) class='Hi'>proof, which can be formalized in IΔ0 + Δ0EQ, of the fact that every prime of the form 4n + 1 is the sum of two squares. (shrink)

Can visual thinking be a means of discovery in elementary analysis, as well as a means of illustration and a stimulus to discovery? The answer to the corresponding question for geometry and arithmetic seems to be ‘yes’ (Giaquinto [1992], [1993]), and so a positive answer might be expected for elementary analysis too. But I argue here that only in a severely restricted range of cases can visual thinking be a means of discovery in analysis. Examination of persuasive visual (...) routes to two simple theorems (Rolle, Bolzano) shows that they are not ways of discovering the theorems; the type of visual thinking involved can never be used to discover analytic theorems of a certain generality. The hypothesis that visual thinking is never a means of discovering the existence or nature of the limit of some infinite process is considered, and a likely counter-example is set out. It is still possible that restricted theorems can be discovered visually: an example from Littlewood is examined in detail and not found wanting. Even when visual thinking is not a means of discovery it can provide the idea for a proof in a direct way; an example is presented (Intermediate Value Theorem). In conclusion: it may be possible to discover theorems in elementary real analysis by visual means, but only theorems of a restricted kind; however, visual thinking in analysis can be very useful in other ways. (shrink)

Filling the need for an accessible, carefully structured introductory text in symbolic logic, Modern Logic has many features designed to improve students' comprehension of the subject, including a proof system that is the same as the award-winning computer program MacLogic, and a special appendix that shows how to use MacLogic as a teaching aid. There are graded exercises at the end of each chapter--more than 900 in all--with selected answers at the end of the book. Unlike competing texts, Modern (...) Logic gives equal weight to semantics and proof theory and explains their relationship, and develops in detail techniques for symbolizing natural language in first-order logic. After a general introduction featuring the notion of logical form, the book offers sections on classical sentential logic, monadic predicate logic, and full first-order logic with identity. A concluding section deals with extensions of and alternatives to classical logic, including modal logic, intuitionistic logic, and fuzzy logic. For students of philosophy, mathematics, computer science, or linguistics, Modern Logic provides a thorough understanding of basic concepts and a sound basis for more advanced work. (shrink)

The use of figurate numbers (e. g. in the context of elementary number theory) can be considered a heuristic in the field of problem solving or proving. In this paper, we want to discuss this heuristic from the perspectives of the semiotic theory of Peirce (“diagrammatic reasoning” and “collateral knowledge”) and cognitive psychology (“schema theory” and “Gestalt psychology”). We will make use of several results taken from our research to illustrate first-year students’ problems when dealing with figurate numbers in (...) the context of proving. The considerations taken from both theoretical perspectives will help to partly explain such phenomena. It will be shown that the use of figurate numbers must not be considered to be any kind of help for learners or some way of ‘easy’ mathematics. Working in this representational system has to be learned and practiced as another kind of knowledge is necessary for working with figurate numbers. The named findings also touch upon the concept of ‘proofs that explain’. Finally, we will highlight some implications for teaching and point to a number of demands for future research. (shrink)

The interpretation of propositions in Lukasiewicz's infinite-valued calculus as answers in Ulam's game with lies--the Boolean case corresponding to the traditional Twenty Questions game--gives added interest to the completeness theorem. The literature contains several different proofs, but they invariably require technical prerequisites from such areas as model-theory, algebraic geometry, or the theory of ordered groups. The aim of this paper is to provide a self-contained proof, only requiring the rudiments of algebra and convexity in finite-dimensional vector spaces.

We provide a new and elementary proof of strong normalization for the lambda calculus of intersection types. It uses no strong method, like for instance Tait-Girard reducibility predicates, but just simple induction on type complexity and derivation length and thus it is obviously formalizable within first order arithmetic. To obtain this result, we introduce a new system for intersection types whose rules are directly inspired by the reduction relation. Finally, we show that not only the set of strongly (...) normalizing terms of pure lambda calculus can be characterized in this system, but also that a straightforward modification of its rules allows to characterize the set of weakly normalizing terms. (shrink)

An extensive literature overlapping economics, statistical decision theory and finance, contrasts expected utility [EU] with the more recent framework of mean–variance (MV). A basic proposition is that MV follows from EU under the assumption of quadratic utility. A less recognized proposition, first raised by Markowitz, is that MV is fully justified under EU, if and only if utility is quadratic. The existing proof of this proposition relies on an assumption from EU, described here as “Buridan’s axiom” after the French (...) philosopher’s fable of the ass that starved out of indifference between two bales of hay. To satisfy this axiom, MV must represent not only “pure” strategies, but also their probability mixtures, as points in the (σ, μ) plane. Markowitz and others have argued that probability mixtures are represented sufficiently by (σ, μ) only under quadratic utility, and hence that MV, interpreted as a mathematical re-expression of EU, implies quadratic utility. We prove a stronger form of this theorem, not involving or contradicting Buridan’s axiom, nor any more fundamental axiom of utility theory. (shrink)

In this paper we show some non-elementary speed-ups in logic calculi: Both a predicative second-order logic and a logic for fixed points of positive formulas are shown to have non-elementary speed-ups over first-order logic. Also it is shown that eliminating second-order cut formulas in second-order logic has to increase sizes of proofs super-exponentially, and the same in eliminating second-order epsilon axioms. These are proved by relying on results due to P. Pudlák.

We present a manuscript of Paul Lorenzen that provides a proof of consistency for elementary number theory as an application of the construction of the free countably complete pseudocomplemented semilattice over a preordered set. This manuscript rests in the Oskar-Becker-Nachlass at the Philosophisches Archiv of Universität Konstanz, file OB 5-3b-5. It has probably been written between March and May 1944. We also compare this proof to Gentzen's and Novikov's, and provide a translation of the manuscript.

Written for any motivated reader with a high-school knowledge of mathematics, and the discipline to follow logical arguments, this book presents the proofs for revolutionary impossibility theorems in an accessible way, with less jargon and notation, and more background, intuition, examples, explanations, and exercises.

In this article, we report a study in which 109 research-active mathematicians were asked to judge the validity of a purported proof in undergraduate calculus. Significant results from our study were as follows: (a) there was substantial disagreement among mathematicians regarding whether the argument was a valid proof, (b) applied mathematicians were more likely than pure mathematicians to judge the argument valid, (c) participants who judged the argument invalid were more confident in their judgments than those who judged (...) it valid, and (d) participants who judged the argument valid usually did not change their judgment when presented with a reason raised by other mathematicians for why the proof should be judged invalid. These findings suggest that, contrary to some claims in the literature, there is not a single standard of validity among contemporary mathematicians. (shrink)

In this paper, I attempt a reconstruction of the theory of intersections in the geometry of Euclid. It has been well known, at least since the time of Pasch onward, that in the Elements there are no explicit principles governing the existence of the points of intersections between lines, so that in several propositions of Euclid the simple crossing of two lines (two circles, for instance) is regarded as the actual meeting of such lines, it being simply assumed that the (...) point of their intersection exists. Such assumptions are labelled, today, as implicit claims about the continuity of the lines, or about the continuity of the underlying space. Euclid’s proofs, therefore, would seem to have some demonstrative gaps that need to be filled by a set of continuity axioms (as we do, in fact, find in modern axiomatizations).I show that Euclid’s theory of intersections was not in fact based on any notion of continuity at all. This is not only because Greek concepts of continuity (such as the Aristotelian ones) were largely insufficient to ground a geometrical theory of intersections, but also, at a deeper level, because continuity was simply not regarded as a notion that had any role to play in the latter theory. Had Euclid been asked to explain why the points of intersections of lines and circles should exist, it would have never occurred to him to mention continuity in this connection. Ancient geometry was very different from ours, and it is only our modern views on continuity that tend to give rise to the expectation that this latter must be included in the foundations of elementary mathematics.We may hope to reconstruct Euclid’s views on intersections if we undertake a critical examination both of the extension and of the limits of ancient diagrammatic practices. This is tantamount to attempting to understand to what extent the existence of an intersection point may be inferred just from the inspection of a diagram, and in which cases we need rather to supplement such inference by propositional rules. This leads us to discuss Euclid’s definition of a point, and to work out the details of the complex interaction between diagrams and text in ancient geometry. We will see, then, that Euclid may have possessed a theory of intersections that was sufficiently rigorous to dispel the main objections that could be advanced in antiquity. (shrink)

The paper generalises Goldblatt's completeness proof for Lemmon–Scott formulas to various modal propositional logics without classical negation and without ex falso, up to positive modal logic, where conjunction and disjunction, andwhere necessity and possibility are respectively independent.Further the paper proves definability theorems for Lemmon–Scottformulas, which hold even in modal propositional languages without negation and without falsum. Both, the completeness theorem and the definability theoremmake use only of special constructions of relations,like relation products. No second order logic, no general frames (...) are involved. (shrink)

In practice, mathematical proofs are most often the result of careful planning by the agents who produced them. As a consequence, each mathematical proof inherits a plan in virtue of the way it is produced, a plan which underlies its “architecture” or “unity”. This paper provides an account of plans and planning in the context of mathematical proofs. The approach adopted here consists in looking for these notions not in mathematical proofs themselves, but in the agents who produced them. (...) The starting point is to recognize that to each mathematical proof corresponds a proof activity which consists of a sequence of deductive inferences—i.e., a sequence of epistemic actions—and that any written mathematical proof is only a report of its corresponding proof activity. The main idea to be developed is that the plan of a mathematical proof is to be conceived and analyzed as the plan of the agent(s) who carried out the corresponding proof activity. The core of the paper is thus devoted to the development of an account of plans and planning in the context of proof activities. The account is based on the theory of planning agency developed by Michael Bratman in the philosophy of action. It is fleshed out by providing an analysis of the notions of intention—the elementary components of plans—and practical reasoning—the process by which plans are constructed—in the context of proof activities. These two notions are then used to offer a precise characterization of the desired notion of plan for proof activities. A fruitful connection can then be established between the resulting framework and the recent theme of modularity in mathematics introduced by Jeremy Avigad. This connection is exploited to yield the concept of modular presentations of mathematical proofs which has direct implications for how to write and present mathematical proofs so as to deliver various epistemic benefits. The account is finally compared to the technique of proof planning developed by Alan Bundy and colleagues in the field of automated theorem proving. The paper concludes with some remarks on how the framework can be used to provide an analysis of understanding and explanation in the context of mathematical proofs. (shrink)

The cofinality quantifiers were introduced by Shelah as an example of a compact logic stronger than first-order logic. We show that the classes of models axiomatized by these quantifiers can be turned into an Abstract Elementary Class by restricting to positive and deliberate uses. Rather than using an ad hoc proof, we give a general framework of abstract Skolemizations. This method gives a uniform proof that a wide rang of classes are Abstract Elementary Classes.

This book continues from where the authors' previous book, Structural Proof Theory, ended. It presents an extension of the methods of analysis of proofs in pure logic to elementary axiomatic systems and to what is known as philosophical logic. A self-contained brief introduction to the proof theory of pure logic is included that serves both the mathematically and philosophically oriented reader. The method is built up gradually, with examples drawn from theories of order, lattice theory and (...) class='Hi'>elementary geometry. The aim is, in each of the examples, to help the reader grasp the combinatorial behaviour of an axiom system, which typically leads to decidability results. The last part presents, as an application and extension of all that precedes it, a proof-theoretical approach to the Kripke semantics of modal and related logics, with a great number of new results, providing essential reading for mathematical and philosophical logicians. (shrink)

Elementary submodels of some initial segment of the set-theoretic universe are useful in order to prove certain theorems in general topology as well as in algebra. As an illustration we give proofs of two theorems due to Arkhangelskii concerning cardinal invariants of compact spaces.

In this paper, I explore whether elementary classical mechanics adheres to the Principle of Composition of Causes as Mill claimed and as certain contemporary authors still seem to believe. Among other things, I provide a proof that if one reads Mill’s description of the principle literally, it does not hold in any general sense. In addition, I explore a separate notion of Composition of Causes and note that it too does not hold in elementary classical mechanics. Among (...) the major morals is that there is no utility to describing classical mechanics in terms of Composition of Causes. This is both because the stated principles do not hold and because when one describes what actually does hold in classical mechanics in terms of the Composition of Causes, one introduces misleading associations that can generate errors just as claimed by Russell. (shrink)

A central problem in the interpretation of non-relativistic quantum mechanics is to relate the conceptual structure of the theory to the classical idea of the state of a physical system. This paper approaches the problem by presenting an analysis of the notion of an elementary physical proposition. The notion is shown to be realized in standard formulations of the theory and to illuminate the significance of proofs of the impossibility of hidden variable extensions. In the interpretation of quantum mechanics (...) that emerges from this analysis, the philosophically distinctive features of the theory derive from the fact that it seeks to represent a reality of which complete knowledge is essentially unattainable. (shrink)

We show that for any uncountable cardinal λ, the category of sets of cardinality at least λ and monomorphisms between them cannot appear as the category of points of a topos, in particular is not the category of models of a ${L_{\infty,\omega }}$-theory. More generally we show that for any regular cardinal $\kappa < \lambda$ it is neither the category of κ-points of a κ-topos, in particular, nor the category of models of a ${L_{\infty,\kappa }}$-theory.The proof relies on the (...) construction of a categorified version of the Scott topology, which constitute a left adjoint to the functor sending any topos to its category of points and the computation of this left adjoint evaluated on the category of sets of cardinality at least λ and monomorphisms between them. The same techniques also apply to a few other categories. At least to the category of vector spaces of with bounded below dimension and the category of algebraic closed fields of fixed characteristic with bounded below transcendence degree. (shrink)

In this paper we calibrate the exact proof-theoretic strength of Kruskal's theorem, thereby giving, in some sense, the most elementary proof of Kruskal's theorem. Furthermore, these investigations give rise to ordinal analyses of restricted bar induction.

Now available in paperback, this acclaimed book introduces categories and elementary toposes in a manner requiring little mathematical background. It defines the key concepts and gives complete elementary proofs of theorems, including the fundamental theorem of toposes and the sheafification theorem. It ends with topos theoretic descriptions of sets, of basic differential geometry, and of recursive analysis.

This book introduces students to the art and craft of writing proofs, beginning with the basics of writing proofs and logic, and continuing on with more in-depth issues and examples of creating proofs in different parts of mathematics, as well as introducing proofs-of-correctness for algorithms. The creation of proofs is covered for theorems in both discrete and continuous mathematics, and in difficulty ranging from elementary to beginning graduate level. Just beyond the standard introductory courses on calculus, theorems and proofs (...) become central to mathematics. Students often find this emphasis difficult and new. This book is a guide to understanding and creating proofs. It explains the standard "moves" in mathematical proofs: direct computation, expanding definitions, proof by contradiction, proof by induction, as well as choosing notation and strategies. (shrink)

Given two infinite binary sequences A,B we say that B can compress at least as well as A if the prefix-free Kolmogorov complexity relative to B of any binary string is at most as much as the prefix-free Kolmogorov complexity relative to A, modulo a constant. This relation, introduced in Nies [14] and denoted by A≤LKB, is a measure of relative compressing power of oracles, in the same way that Turing reducibility is a measure of relative information. The equivalence classes (...) induced by ≤LK are called LK degrees and there is a least degree containing the oracles which can only compress as much as a computable oracle, also called the ‘low for K’ sets. A well-known result from Nies [14] states that these coincide with the K-trivial sets, which are the ones whose initial segments have minimal prefix-free Kolmogorov complexity. We show that with respect to ≤LK, given any non-trivial sets X,Y there is a computably enumerable set A which is not K-trivial and it is below X,Y. This shows that the local structures of and Turing degrees are not elementarily equivalent to the corresponding local structures in the LK degrees. It also shows that there is no pair of sets computable from the halting problem which forms a minimal pair in the LK degrees; this is sharp in terms of the jump, as it is known that there are sets computable from which form a minimal pair in the LK degrees. We also show that the structure of LK degrees below the LK degree of the halting problem is not elementarily equivalent to the or structures of LK degrees. The proofs introduce a new technique of permitting below a set that is not K-trivial, which is likely to have wider applications. (shrink)

We explain the elementary mistake made by John S. Bell in the proof of his famous ``theorem.''.

We will study patterns which occur when considering how Σ 1 -elementary substructures arise within hierarchies of structures. The order in which such patterns evolve will be seen to be independent of the hierarchy of structures provided the hierarchy satisfies some mild conditions. These patterns form the lowest level of what we call patterns of resemblance . They were originally used by the author to verify a conjecture of W. Reinhardt concerning epistemic theories 449–460; Ann. Pure Appl. Logic, to (...) appear), but their relationship to axioms of infinity and usefulness for ordinal analysis were manifest from the beginning. This paper is the first part of a series which provides an introduction to an extensive program including the ordinal analysis of set theories. Future papers will conclude the introduction and establish, among other things, that notations we will derive from the patterns considered here represent the proof-theoretic ordinal of the theory KPℓ 0 or, equivalently, Π 1 1 −CA 0. (shrink)

We present here an approach to the fine structure of L based solely on elementary model theoretic ideas, and illustrate its use in a proof of Global Square in L. We thereby avoid the Lévy hierarchy of formulas and the subtleties of master codes and projecta, introduced by Jensen [3] in the original form of the theory. Our theory could appropriately be called ”Hyperfine Structure Theory”, as we make use of a hierarchy of structures and hull operations which (...) refines the traditional Lα -or Jα-sequences with their Σn-hull operations.§1. Introduction. In 1938, K. Gödel defined the model L of set theory to show the relative consistency of Cantor's Continuum Hypothesis. L is defined as a unionof initial segments which satisfy: L0 = ∅, Lλ = ∪α<λLα for limit ordinals λ, and, crucially, Lα + 1 = the collection of 1st order definable subsets of Lα. Since every transitive model of set theory must be closed under 1st order definability, L turns out to be the smallest inner model of set theory. Thus it occupies the central place in the set theoretic spectrum of models.The proof of the continuum hypothesis in L is based on the very uniform hierarchical definition of the L-hierarchy. The Condensation Lemma states that if π : M → Lα is an elementary embedding, M transitive, then some ; the lemma can be proved by induction on α. If a real, i.e., a subset of ω, is definable over some Lα,then by a Löwenheim-Skolem argument it is definable over some countable M as above, and hence over some, < ω1. This allows one to list the reals in L in length ω1 and therefore proves the Continuum Hypothesis in L. (shrink)

An Elementary Transition to Abstract Mathematics will help students move from introductory courses to those where rigor and proof play a much greater role. The text is organized into five basic parts: the first looks back on selected topics from pre-calculus and calculus, treating them more rigorously, and it covers various proof techniques; the second part covers induction, sets, functions, cardinality, complex numbers, permutations, and matrices; the third part introduces basic number theory including applications to cryptography; the (...) fourth part introduces key objects from abstract algebra; and the final part focuses on polynomials. Features: The material is presented in many short chapters, so that one concept at a time can be absorbed by the student. Two "looking back" chapters at the outset (pre-calculus and calculus) are designed to start the student's transition by working with familiar concepts. Many examples of every concept are given to make the material as concrete as possible and to emphasize the importance of searching for patterns. A conversational writing style is employed throughout in an effort to encourage active learning on the part of the student. (shrink)

We introduce an operational set theory in the style of [5] and [16]. The theory we develop here is a theory of constructive sets and operations. One motivation behind constructive operational set theory is to merge a constructive notion of set ([1], [2]) with some aspects which are typical of explicit mathematics [14]. In particular, one has non-extensional operations (or rules) alongside extensional constructive sets. Operations are in general partial and a limited form of self{application is permitted. The system we (...) introduce here is a fully explicit, nitely axiomatised system of constructive sets and operations, which is shown to be as strong as HA. (shrink)

Let KP- be the theory resulting from Kripke-Platek set theory by restricting Foundation to Set Foundation. Let G: V → V (V:= universe of sets) be a ▵0-definable set function, i.e. there is a ▵0-formula φ(x, y) such that φ(x, G(x)) is true for all sets x, and $V \models \forall x \exists!y\varphi (x, y)$ . In this paper we shall verify (by elementary proof-theoretic methods) that the collection of set functions primitive recursive in G coincides with the (...) collection of those functions which are Σ1-definable in KP- + Σ1-Foundation + ∀ x ∃!yφ (x, y). Moreover, we show that this is still true if one adds Π1-Foundation or a weak version of ▵0-Dependent Choices to the latter theory. (shrink)

A new case of Shelah's eventual categoricity conjecture is established: Let be an abstract elementary class with amalgamation. Write and. Assume that is H2‐tame and has primes over sets of the form. If is categorical in some, then is categorical in all. The result had previously been established when the stronger locality assumptions of full tameness and shortness are also required. An application of the method of proof of the mentioned result is that Shelah's categoricity conjecture holds in (...) the context of homogeneous model theory (this was known, but our proof gives new cases): If D be a homogeneous diagram in a first‐order theory T and D is categorical in a, then D is categorical in all. (shrink)

We give a sharper version of a theorem of Rosický, Trnková and Adámek [13], and a new proof of a theorem of Rosický [12], both about colimits in categories of structures. Unlike the original proofs, which use category-theoretic methods, we use set-theoretic arguments involving elementary embeddings given by large cardinals such as $\alpha$-strongly compact and $C^{(n)}$-extendible cardinals.

In a previous paper, an elementary and thoroughly arithmetical proof of Fermat’s last theorem by induction has been demonstrated if the case for “n = 3” is granted as proved only arithmetically (which is a fact a long time ago), furthermore in a way accessible to Fermat himself though without being absolutely and precisely correct. The present paper elucidates the contemporary mathematical background, from which an inductive proof of FLT can be inferred since its proof for (...) the case for “n = 3” has been known for a long time. It needs “Hilbert mathematics”, which is inherently complete unlike the usual “Gödel mathematics”, and based on “Hilbert arithmetic” to generalize Peano arithmetic in a way to unify it with the qubit Hilbert space of quantum information. An “epoché to infinity” (similar to Husserl’s “epoché to reality”) is necessary to map Hilbert arithmetic into Peano arithmetic in order to be relevant to Fermat’s age. Furthermore, the two linked semigroups originating from addition and multiplication and from the Peano axioms in the final analysis can be postulated algebraically as independent of each other in a “Hamilton” modification of arithmetic supposedly equivalent to Peano arithmetic. The inductive proof of FLT can be deduced absolutely precisely in that Hamilton arithmetic and the pransfered as a corollary in the standard Peano arithmetic furthermore in a way accessible in Fermat’s epoch and thus, to himself in principle. A future, second part of the paper is outlined, getting directed to an eventual proof of the case “n=3” based on the qubit Hilbert space and the Kochen-Specker theorem inferable from it. (shrink)

Now much revised since its first appearance in 1941, this book, despite its brevity, is notable for its scope and rigor. It provides a single strand of simple techniques for the central business of modern logic. Basic formal concepts are explained, the paraphrasing of words into symbols is treated at some length, and a testing procedure is given for truth-function logic along with a complete proof procedure for the logic of quantifiers. Fully one third of this revised edition is (...) new, and presents a nearly complete turnover in crucial techniques of testing and proving, some change of notation, and some updating of terminology. The study is intended primarily as a convenient encapsulation of minimum essentials, but concludes by giving brief glimpses of further matters. (shrink)

This paper propounds the following theses: 1). that the traditional focus on the Blackstone ratio of errors as a device for setting the criminal standard of proof is ill-conceived, 2). that the preoccupation with the rate of false convictions in criminal trials is myopic, and 3). that the key ratio of interest, in judging the political morality of a system of criminal justice, involves the relation between the risk that an innocent person runs of being falsely convicted of a (...) serious crime and the risk of being criminally victimized by someone who was falsely acquitted. (shrink)

The basic motivation behind this work is to tie together various computational complexity classes, whether over different domains such as the naturals or the reals, or whether defined in different manners, via function algebras (Real Recursive Functions) or via Turing Machines (Computable Analysis). We provide general tools for investigating these issues, using two techniques we call approximation and lifting. We use these methods to obtain two main theorems. First, we provide an alternative proof of the result from Campagnolo et (...) al. (J Complex 18:977–1000, 2002), which precisely relates the Kalmar elementary computable functions to a function algebra over the reals. Second, we build on that result to extend a result of Bournez and Hainry (Theor Comput Sci 348(2–3):130–147, 2005), which provided a function algebra for the ${\mathcal{C}}^2$ real elementary computable functions; our result does not require the restriction to ${\mathcal{C}}^2$ functions. In addition to the extension, we provide an alternative approach to the proof. Their proof involves simulating the operation of a Turing Machine using a function algebra. We avoid this simulation, using a technique we call lifting, which allows us to lift the classic result regarding the elementary computable functions to a result on the reals. The two new techniques bring a different perspective to these problems, and furthermore appear more easily applicable to other problems of this sort. (shrink)

§1. Introduction. I dedicate this essay to the two-dozen-odd people whose refutations of Cantor's diagonal argument have come to me either as referee or as editor in the last twenty years or so. Sadly these submissions were all quite unpublishable; I sent them back with what I hope were helpful comments. A few years ago it occurred to me to wonder why so many people devote so much energy to refuting this harmless little argument—what had it done to make them (...) angry with it? So I started to keep notes of these papers, in the hope that some pattern would emerge.These pages report the results. They might be useful for editors faced with similar problem papers, or even for the authors of the papers themselves. But the main message to reach me is that there are several points of basic elementary logic that we usually teach and explain very badly, or not at all.In 1995 an engineer named William Dilworth, who had published a refutation of Cantor's argument in the Transactions of the Wisconsin Academy of Sciences, Arts and Letters, sued for libel a mathematician named Underwood Dudley who had called him a crank. (shrink)

We consider the problem of the product finite model property for binary products of modal logics. First we give a new proof for the product finite model property of the logic of products of Kripke frames, a result due to Shehtman. Then we modify the proof to obtain the same result for logics of products of Kripke frames satisfying any combination of seriality, reflexivity and symmetry. We do not consider the transitivity condition in isolation because it leads to (...) infinity axioms when taking products. (shrink)

There is a very simple way in which the safe/normal variable discipline of Bellantoni–Cook recursion [S. Bellantoni, S. Cook, A new recursion theoretic characterization of the polytime functions, Computational Complexity 2 97–110] can be imposed on arithmetical theories like PA: quantify over safes and induct on normals. This weakens the theory severely, so that the provably recursive functions become more realistically computable . Earlier results of D. Leivant [Intrinsic theories and computational complexity, in: D. Leivant , Logic and Computational Complexity, (...) Lecture Notes in Computer Science, vol. 960, Springer-Verlag, 1995, pp. 177–194] are re-worked and extended in this new context, giving proof-theoretic characterizations of complexity classes between Grzegorczyk’s E2 and E3. (shrink)